package Tree;

public class _623_AddOneRowtoTree {
    int depth;
    int val;
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        this.depth = d;
        this.val = v;
        if (d == 1) {
            TreeNode t = new TreeNode(v);
            t.left = root;
            return t;
        } else {
            helper(root, 1);
            return root;
        }
    }

    public void helper(TreeNode root, int level) {
        if (root != null) {
            //level one is special.
            if (level == depth - 1) {
                TreeNode newlNode = new TreeNode(val);
                TreeNode newrNode = new TreeNode(val);
                if (root.left != null || root.right != null) {
                    TreeNode tlNode = root.left;
                    TreeNode trNode = root.right;
                    newlNode.left = tlNode;
                    newrNode.right = trNode;
                }
                root.left = newlNode;
                root.right = newrNode;
            } else {
                helper(root.left, level + 1);
                helper(root.right, level + 1);
            }
        }
    }
}
